# GNAFU - "Ground, Navy and Air Fuck-Up" Copyright (C) 2008 k0wax <k0waxk0wax@gmail.com>
#
# This file is part of GNAFU.
#
# GNAFU is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# GNAFU is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with GNAFU.  If not, see <http://www.gnu.org/licenses/>.

from __future__ import division, absolute_import
from src import geom, field
from src import game

gcost_straight = 10 # straight unit move cost
gcost_diagonal = 14 # diagonal unit move cost

class Node(object):
    def __init__(self, x, y):
        self.x, self.y = x, y
        self.fs = 0
        self.parent = None
    def __cmp__(self, o):
        return 0 if self.x == o.x and self.y == o.y else 1 # fixme
    def __repr__(self):
        return '<Node %d, %d, fs=%d>' % (self.x, self.y, self.fs)
    
def cell2node(cell):
    return Node([cell.x, cell.y])

def neighbours(x, y):
    fw, fh = game.field.w, game.field.h
    r = ([x,y+1], [x+1,y+1], [x+1,y],
            [x+1,y-1], [x,y-1], [x-1,y-1],
            [x-1,y], [x-1,y+1])
    # if need wrapping
    if (x+1 >= fw or x-1 < 0) or (y+1 >= fh or y-1 < 0):
        r = [(x[0]%fw, x[1]%fh) for x in r]
    return r

def get_fscore_func(start, goal): # fixme
    """returns fscore calculation function by field_delta (fd)"""
    fw, fh = game.field.w, game.field.h
    fd = geom.field_delta(start.x, start.y, goal.x, goal.y, fw, fh)
    func_type = ('xlyu' if fd[0] < 0 else 'xryu') if fd[1] >= 0 else \
                ('xlyd' if fd[0] < 0 else 'xryd')
    h = {'xlyu': lambda a, b: gcost_straight * ((a.x - b.x)%fw + abs((b.y - a.y)%fh)),
         'xryu': lambda a, b: gcost_straight * (abs((b.x - a.x)%fw) + abs((b.y - a.y)%fh)),
         'xlyd': lambda a, b: gcost_straight * ((a.x - b.x)%fw + abs((a.y - b.y)%fh)),
         'xryd': lambda a, b: gcost_straight * (abs((b.x - a.x)%fw) + (a.y - b.y)%fh), 
         }
    return h[func_type]

def get_lowest_fscore_node(l): #fixme: use sorting
    ret = l[0]
    for x in l:
        ret = x if x.fs < ret.fs else ret
    return ret

def traceback_path(n):
    while n.parent:
        yield n
        n = n.parent
    yield n
    
def path(start, goal, **kw):
    start = Node(*start)
    goal = Node(*goal)
    cset = [] # closed set
    oset = [start] # open set
    path = []
    fscore = get_fscore_func(start, goal)
    check_z = False
    if 'surface_type' in kw:
        zmin, zmax = field.surface_minmax_levels[kw['surface_type']]
        check_z = True
    print 'FROM', start, 'TO', goal
    while len(oset) > 0:
        #print 'iter'
        x = get_lowest_fscore_node(oset)
        if x == goal:
            print 'GOAL'
            path = list(traceback_path(x))
            path.pop()
            return path
        oset.remove(x)
        cset.append(x)
        for y in [Node(*pos) for pos in neighbours(x.x, x.y)]: # get a slice
            if y in cset: # fixme
                continue # already done
            if check_z:
                lev = game.field.zlevel[y.x][y.y]
                if not (lev >= zmin and lev <= zmax):
                    continue # `closed`
            y.parent = x
            y.fs += fscore(y, goal)
            if y not in oset:
                oset.append(y) # process node in next iter
    return False
    
if __name__ == '__main__':
    path = path((1, 1), (5, 5))
